#ifndef __DICCTRIE_H__
#define __DICCTRIE_H__

#include "../aed2/aed2.h"

#include <iostream>
using namespace std;

#define TAMANIO_DICCIONARIO 256

namespace aed2{

    /**
     * Esta clase implementa el modulo DiccTrie, por cuestions practicas solo
     * acepta claves con un alfabeto de letras de la 'a' a la 'z'.
     */
	template <class T>
	class DiccTrie{
	
	public:
	    
	    /**
	     * Crea un nuevo DiccTrie
	     *
	     * PRE : Ninguna.
		 * POST: Se crea un DiccTrie vacio.
		 * 	
		 * @Parámetros: Ninguno.
		 * 
		 * @Devuelve: Nada.
		 */
	    DiccTrie();
	    
	    /**
	     * Crea un nuevo DiccTrie
	     *
	     * PRE : Ninguna.
		 * POST: Se destruye el DiccTrie
		 * 	
		 * @Parámetros: Ninguno.
		 * 
		 * @Devuelve: Nada.
		 */
	    ~DiccTrie();
	    
	    /**
	     * Define una entrada del diccionario.
	     *
	     * PRE : La clave tiene que tener solo letras de a a la z en minuscula.
		 * POST: La entrada queda definida.
		 * 	
		 * @Parámetros:
		 *      clave La clave
		 *      significado El valor
		 * 
		 * @Devuelve: Nada.
		 */
	    void Definir(const String & clave, const T & significado);
	    
	    /**
	     * Retorna true si la entrada esta definida o no.
	     *
	     * PRE : La clave tiene que tener solo letras de a a la z en minuscula.
		 * POST: Ninguna.
		 * 	
		 * @Parámetros: 
		 *      clave La clave
		 * 
		 * @Devuelve: Si la clave esta definida o no.
		 */
	    bool Definido(const String &clave) const;
	    
	    /**
		 * Retorna el valor de una entrada del diccionario.
		 *
		 * PRE : La clave tiene que tener solo letras de a a la z en minuscula
		 *       y estar definida.
		 * POST: Ninguna.
		 *
		 * @Parámetros:
		 *      clave La clave
		 *
		 * @Devuelve: El valor.
		 */
		T& Obtener(const String &clave);

    private:
        
        struct Nodo;
        
        /**
         * Representacion interna
         */
        Nodo *raiz;
    
        //////////////////////////
        //Operaciones canceladas//
        //////////////////////////
        
        /**
         * Sin constructor por copia
         */
        DiccTrie(const DiccTrie<T> &otro) {
            assert(false);
        }
        
        /**
         * Sin asignacion
         */
        DiccTrie<T> operator=(const DiccTrie<T> &otro) {
            assert(false);

        }
        /////////////////////////////////
        //Fin de operaciones canceladas//
        /////////////////////////////////

    
        /**
         *Definicion del nodo.
         */
        struct Nodo {

        public:
            
            Nodo *proximasLetras[TAMANIO_DICCIONARIO];
            T *elemento;
            
            /**
             * Sin constructor por defecto.
             */
            Nodo() : elemento(NULL) {
                for (unsigned int i = 0; i < TAMANIO_DICCIONARIO; i += 1) {
                    proximasLetras[i] = NULL;
                }
            }

            /**
             * Destruye el nodo.
             */
            ~Nodo() {
				delete elemento;
                elemento = NULL;

                for (unsigned int i = 0; i < TAMANIO_DICCIONARIO; i += 1) {
                    if (proximasLetras[i] != NULL) {
                        delete proximasLetras[i];
                        proximasLetras[i] = NULL;
                    }
                }
            }
        
        private:
            
            //////////////////////////
            //Operaciones canceladas//
            //////////////////////////
            
            /**
             * Sin constructor por copia.
             */
            Nodo(const Nodo &otro) {
                assert(false);
            }
            
            /**
             * Sin asignacion.
             */
            Nodo operator=(const Nodo &otro) {
                assert(false);
            }
            
            /////////////////////////////////
            //Fin de operaciones canceladas//
            /////////////////////////////////
            
        };
	
	};
	
	/**
	 * Implementaciones
	 */
	
	template <typename T>
	DiccTrie<T>::DiccTrie() {
	    raiz = new Nodo();
	}
	
	template <typename T>
	DiccTrie<T>::~DiccTrie() {
	    delete raiz;
	    raiz = NULL;
	}
	
	template <typename T>
	void DiccTrie<T>::Definir(const String &clave, const T &significado) {
	
	    unsigned int i = 0;
	    Nodo *nodo = raiz;
	    Nodo *tmpNodo = NULL;
	    char c;
	    
	    while (i < clave.length()) {
	    
	        c = clave[i];
	        tmpNodo = nodo->proximasLetras[(int) c];
	        
	        if (tmpNodo == NULL) {
	            tmpNodo = new Nodo();
	            nodo->proximasLetras[(int) c] = tmpNodo;
	        }
            
            nodo = tmpNodo;
	        i += 1;
	    }
	    
	    if (nodo->elemento != NULL) {
	    	delete nodo->elemento;
	    }

	    nodo->elemento = new T(significado);
	}
	
	template <typename T>
	bool DiccTrie<T>::Definido(const String &clave) const {
	
    	unsigned int i = 0;
	    Nodo *nodo = raiz;
	    char c;
	    
	    while ((i < clave.length()) && (nodo != NULL)) {
	        c = clave[i];
	        nodo = nodo->proximasLetras[(int) c];
	        i += 1;
	    }
	    
	    return ((nodo != NULL) && (nodo->elemento != NULL));
	}
	
    template <typename T>
	T &DiccTrie<T>::Obtener(const String &clave) {

    	unsigned int i = 0;
	    Nodo *nodo = raiz;
	    char c;

	    while (i < clave.length()) {
	        c = clave[i];
	        nodo = nodo->proximasLetras[(int) c];
	        i += 1;
	    }

	    return *(nodo->elemento);
	}

}

#endif /* __DICCTRIE_H__ */
